/*
 * Copyright (C) 2007 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dx.util;

/**
 * Utilities for treating {@code int[]}s as bit sets.
 */
public final class Bits {

	/**
	 * This class is uninstantiable.
	 */
	private Bits() {
		// This space intentionally left blank.
	}

	/**
	 * Constructs a bit set to contain bits up to the given index (exclusive).
	 * 
	 * @param max
	 *            {@code >= 0;} the maximum bit index (exclusive)
	 * @return {@code non-null;} an appropriately-constructed instance
	 */
	public static int[] makeBitSet(int max) {
		int size = (max + 0x1f) >> 5;
		return new int[size];
	}

	/**
	 * Gets the maximum index (exclusive) for the given bit set.
	 * 
	 * @param bits
	 *            {@code non-null;} bit set in question
	 * @return {@code >= 0;} the maximum index (exclusive) that may be set
	 */
	public static int getMax(int[] bits) {
		return bits.length * 0x20;
	}

	/**
	 * Gets the value of the bit at the given index.
	 * 
	 * @param bits
	 *            {@code non-null;} bit set to operate on
	 * @param idx
	 *            {@code >= 0, < getMax(set);} which bit
	 * @return the value of the indicated bit
	 */
	public static boolean get(int[] bits, int idx) {
		int arrayIdx = idx >> 5;
		int bit = 1 << (idx & 0x1f);
		return (bits[arrayIdx] & bit) != 0;
	}

	/**
	 * Sets the given bit to the given value.
	 * 
	 * @param bits
	 *            {@code non-null;} bit set to operate on
	 * @param idx
	 *            {@code >= 0, < getMax(set);} which bit
	 * @param value
	 *            the new value for the bit
	 */
	public static void set(int[] bits, int idx, boolean value) {
		int arrayIdx = idx >> 5;
		int bit = 1 << (idx & 0x1f);

		if (value) {
			bits[arrayIdx] |= bit;
		} else {
			bits[arrayIdx] &= ~bit;
		}
	}

	/**
	 * Sets the given bit to {@code true}.
	 * 
	 * @param bits
	 *            {@code non-null;} bit set to operate on
	 * @param idx
	 *            {@code >= 0, < getMax(set);} which bit
	 */
	public static void set(int[] bits, int idx) {
		int arrayIdx = idx >> 5;
		int bit = 1 << (idx & 0x1f);
		bits[arrayIdx] |= bit;
	}

	/**
	 * Sets the given bit to {@code false}.
	 * 
	 * @param bits
	 *            {@code non-null;} bit set to operate on
	 * @param idx
	 *            {@code >= 0, < getMax(set);} which bit
	 */
	public static void clear(int[] bits, int idx) {
		int arrayIdx = idx >> 5;
		int bit = 1 << (idx & 0x1f);
		bits[arrayIdx] &= ~bit;
	}

	/**
	 * Returns whether or not the given bit set is empty, that is, whether no
	 * bit is set to {@code true}.
	 * 
	 * @param bits
	 *            {@code non-null;} bit set to operate on
	 * @return {@code true} iff all bits are {@code false}
	 */
	public static boolean isEmpty(int[] bits) {
		int len = bits.length;

		for (int i = 0; i < len; i++) {
			if (bits[i] != 0) {
				return false;
			}
		}

		return true;
	}

	/**
	 * Gets the number of bits set to {@code true} in the given bit set.
	 * 
	 * @param bits
	 *            {@code non-null;} bit set to operate on
	 * @return {@code >= 0;} the bit count (aka population count) of the set
	 */
	public static int bitCount(int[] bits) {
		int len = bits.length;
		int count = 0;

		for (int i = 0; i < len; i++) {
			count += Integer.bitCount(bits[i]);
		}

		return count;
	}

	/**
	 * Returns whether any bits are set to {@code true} in the specified range.
	 * 
	 * @param bits
	 *            {@code non-null;} bit set to operate on
	 * @param start
	 *            {@code >= 0;} index of the first bit in the range (inclusive)
	 * @param end
	 *            {@code >= 0;} index of the last bit in the range (exclusive)
	 * @return {@code true} if any bit is set to {@code true} in the indicated
	 *         range
	 */
	public static boolean anyInRange(int[] bits, int start, int end) {
		int idx = findFirst(bits, start);
		return (idx >= 0) && (idx < end);
	}

	/**
	 * Finds the lowest-order bit set at or after the given index in the given
	 * bit set.
	 * 
	 * @param bits
	 *            {@code non-null;} bit set to operate on
	 * @param idx
	 *            {@code >= 0;} minimum index to return
	 * @return {@code >= -1;} lowest-order bit set at or after {@code idx}, or
	 *         {@code -1} if there is no appropriate bit index to return
	 */
	public static int findFirst(int[] bits, int idx) {
		int len = bits.length;
		int minBit = idx & 0x1f;

		for (int arrayIdx = idx >> 5; arrayIdx < len; arrayIdx++) {
			int word = bits[arrayIdx];
			if (word != 0) {
				int bitIdx = findFirst(word, minBit);
				if (bitIdx >= 0) {
					return (arrayIdx << 5) + bitIdx;
				}
			}
			minBit = 0;
		}

		return -1;
	}

	/**
	 * Finds the lowest-order bit set at or after the given index in the given
	 * {@code int}.
	 * 
	 * @param value
	 *            the value in question
	 * @param idx
	 *            0..31 the minimum bit index to return
	 * @return {@code >= -1;} lowest-order bit set at or after {@code idx}, or
	 *         {@code -1} if there is no appropriate bit index to return
	 */
	public static int findFirst(int value, int idx) {
		value &= ~((1 << idx) - 1); // Mask off too-low bits.
		int result = Integer.numberOfTrailingZeros(value);
		return (result == 32) ? -1 : result;
	}

	/**
	 * Ors bit array {@code b} into bit array {@code a}. {@code a.length} must
	 * be greater than or equal to {@code b.length}.
	 * 
	 * @param a
	 *            {@code non-null;} int array to be ored with other argument.
	 *            This argument is modified.
	 * @param b
	 *            {@code non-null;} int array to be ored into {@code a}. This
	 *            argument is not modified.
	 */
	public static void or(int[] a, int[] b) {
		for (int i = 0; i < b.length; i++) {
			a[i] |= b[i];
		}
	}

	public static String toHuman(int[] bits) {
		StringBuilder sb = new StringBuilder();

		boolean needsComma = false;

		sb.append('{');

		int bitsLength = 32 * bits.length;
		for (int i = 0; i < bitsLength; i++) {
			if (Bits.get(bits, i)) {
				if (needsComma) {
					sb.append(',');
				}
				needsComma = true;
				sb.append(i);
			}
		}
		sb.append('}');

		return sb.toString();
	}
}
